package leetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class IncreasingSubsequences {
	public List<List<Integer>> findSubsequences(int[] nums) {
		int n = nums.length;
		List<List<List<Integer>>> tmp = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			tmp.add(new ArrayList<>());
		}
		Set<String> set = new HashSet<>();
		for (int i = n - 1; i >= 0; i--) {
			// 以nums[i]开始的单独一个列表
			List<Integer> list = new ArrayList<>();
			list.add(nums[i]);
			if (set.add(str(list))) {
				tmp.get(i).add(list);// 如果之前出现过，则不用考虑加入
			}
			// 找到所有nums[i]开始的，
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] <= nums[j]) {
					for (List<Integer> list3 : tmp.get(j)) {
						List<Integer> list2 = new ArrayList<>();
						list2.add(nums[i]);
						list2.addAll(list3);
						if (set.add(str(list2))) {
							tmp.get(i).add(list2);// 检验相同列表
						}
					}
				}
			}
		}
		List<List<Integer>> res = new ArrayList<>();
		for (List<List<Integer>> list : tmp) {
			for (List<Integer> list2 : list) {
				if (list2.size() > 1) {
					res.add(list2);
				}
			}
		}
		return res;
	}

	private String str(List<Integer> list) {
		StringBuilder sbBuilder = new StringBuilder();
		for (Integer integer : list) {
			sbBuilder.append(integer + "_");
		}
		return sbBuilder.toString();
	}

	public static void main(String[] args) {
		int[] nums = { 1, 1, 1, 1, 1 };// { 4, 6, 7, 7 };
		System.out.println(new IncreasingSubsequences().findSubsequences(nums));
	}
}
